package dp;
/**
 * @Description 剑指 Offer 49. 丑数
 * @Author Firenut
 * @Date 2023-01-14 01:34
 */
public class T49_nthUglyNumber {
    // 动态规划
    // 定义:dp[n-1]表示第n个丑数
    // 递推关系: dp[i]=min(dp[a]*2,dp[b]*3,dp[c]*5)
    // 初始值: dp[0]=1 即第一个丑数是1; a b c 初始索引为0
    // 返回值: dp[n-1]
    // k神后面那个动画演示不太好理解
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int a = 0, b = 0, c = 0; //三个指针
        for (int i = 1; i < n; i++) {
            int an = dp[a] * 2, bn = dp[b] * 3, cn = dp[c] * 5;
            dp[i] = Math.min(Math.min(an, bn), cn); //an,bn,cn最小的数作为丑数
            //值相等的需要更新对于的下标索引，以便计算下一个丑数
            if (an==dp[i]) a++;
            if (bn==dp[i]) b++;
            if (cn==dp[i]) c++;
        }
        return dp[n - 1];
    }

    // 我还想直接暴力求呢，结果超时了
    public int nthUglyNumber1(int n) {
        int count = 0;
        for (int i = 1; ; i++) {
            if (isUgly(i)) {
                count++;
                if (count == n) {
                    return i;
                }
            }
        }
    }
    public boolean isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        int[] factors = {3, 5};
        for (int factor : factors) {
            while (num % factor == 0) {
                num /= factor;
            }
        }

        while(num%2==0){
            num>>=1;
        }

        return num == 1;
    }
}
